'''
用遗传算法来解决同样的问题

遗传算法：
1 编码策略
    用随机数列w1 w2 ... w102作为染色体,w1=0,w102=1
    如[0,0.23,0.82,0.45,...,0.87,0.56,1]
    其中位置i表示目标i，位置i的随机数表示目标i再巡回中的顺序
    得到巡回24-4-3-7-57-87-...-52-47-5
2 初始种群
    对于随机产生的初始圈
    C=p1...pu...pv...p102  其中2<=u<v<=101   2<=pu<pv<=101
    交换u v之间的顺序 得到新路径
    C=pi...pv,p(v*1)...p(u+1),pu...p102
    然后记  delta(f)=dnew-dold，若delta(f)<0，则修改路径，直到不能修改为止
3 目标函数
    min sum(dpip(i+1))  i:1~101
4 交叉操作
    采用单点交叉，对于选定的两个父代个体
    f1=p1,p2...p102   f2=p1',p2'...p102' 随机选取第t个基因处为交叉点，交叉得到子代
    s1=p1,p2...pt,p(t+1)'...p102'
    s2=p1',p2'...pt',p(t+1)...p102
5 变异操作
    对于选定的变异个体，随机选取三个整数，满足1<u<v<w<102 把u v之间的基因(包括u v)插到w后面
6 选择
    在父代和子代种群中选择目标函数值最小的M个个体进化到下一代
'''

import pandas as pd
import numpy as np
from math import *
import random
import copy
import time
import matplotlib.pyplot as plt


def swapUandV(c1, c2, S0):
    St = S0[0:c1]
    St.extend(S0[c2:c1 - 1:-1])
    St.extend(S0[c2 + 1:102])
    return St


def cross(t, c1, c2):
    temp = c2[0:t]
    c2[0:t] = c1[0:t]
    c1[0:t] = temp
    return c2, c1


def change(C, u, v, w):
    temp = C[u:v + 1]
    for i in range(u, v + 1):
        del (C[u])
    for i in range(0, len(temp)):
        C.insert(v + i, temp[i])
    return C


data = pd.read_csv('12_1_2.csv')
R = 6371
D = np.zeros((102, 102))
# 填充D矩阵
for i in range(1, 103):
    for j in range(1, 103):
        if i == j:
            continue
        x1 = data['longitude'][i - 1]
        y1 = data['latitude'][i - 1]
        x2 = data['longitude'][j - 1]
        y2 = data['latitude'][j - 1]
        D[i - 1][j - 1] = R * acos(
            cos(radians(x1 - x2)) * cos(radians(y1)) * cos(radians(y2)) + sin(radians(y1)) * sin(radians(y2)))
# 种群个数
w = 50
# 进化代数
g = 100
# 通过改良圈算法选取初始种群
J = np.zeros((50, 102))
for i in range(0, w):
    c = random.sample(range(2, 102), 100)
    c1 = [1]
    c1.extend(c)
    c1.append(102)
    for t in range(0, 102):
        flag = 0
        for m in range(1, 100):
            for n in range(m + 2, 102):
                if (D[c1[m - 1] - 1][c1[n - 1] - 1] + D[c1[m] - 1][c1[n] - 1] < D[c1[m - 1] - 1][c1[m] - 1] +
                        D[c1[n - 1] - 1][c1[n] - 1]):
                    flat = 1
                    c1 = swapUandV(m, n - 1, c1)
        # 无法再修改则退出
        if (flag == 0):
            J[i] = c1
            break
# print(J[:3])
# 转化为染色体编码
J[:, 0] = 0
J[:, 1:102] /= 102
# print(J[:3])
for k in range(0, g):
    # 这里不能A=J 而要J[:]
    A = copy.deepcopy(J)
    c = random.sample(range(1, w + 1), w)
    for i in range(1, w, 2):
        F = 1 + random.randint(1, 101)
        A[i - 1], A[i] = cross(F, A[i - 1], A[i])
    # 找出变异位置
    b = []
    while len(b) == 0:
        y = np.random.rand(1, w).tolist()
        # y是0到1的随机列表 得到b是y中小于0.1元素的索引
        b = [list.index(y[0], i) for i in y[0] if i < 0.1]
    # 变异的染色体
    # 要使用这种语法 B A必须为np.darray 而b要list
    B = A[b]
    # print(len(B))
    for j in range(0, len(b)):
        bw = random.sample(range(1, 102), 3)
        bw.sort()
        B[j] = change(B[j].tolist(), bw[0], bw[1], bw[2])
    # 父代子代种群合在一起
    G = []
    G.extend(J)
    G.extend(A)
    G.extend(B)

    # 重新翻译成序列
    ind1 = np.array(G)
    ind1[:, 0] = 1
    ind1[:, 1:102] *= 102
    ind1 -= 1
    ind1.astype(int)

    num = ind1.shape[0]
    long = np.zeros((1, num))[0]
    for j in range(0, num):
        for i in range(0, 101):
            print( D[int(ind1[j][i])][int(ind1[j][i + 1])])
            long[j] = long[j] + D[int(ind1[j][i])][int(ind1[j][i + 1])]
    slong = sorted(long)
    #print(slong)
    #print(long)
    ind2 = []
    for j in range(0, w):
        ind2.append(list.index(long.tolist(), slong[j]))

    G = np.array(G)
    #print(ind2)
    J = G[ind2]
print(ind2)
path = ind1[ind2].tolist()
flong = slong[0]
px=np.array(data['longitude'].tolist())
py=np.array(data['latitude'].tolist())
xx=[]
yy=[]
for p in range(0,len(path[0])-80):
    xx.append(px[p])
    yy.append(py[p])

print(flong)
print(xx)
print(yy)

plt.xlim(0,70)
plt.ylim(0,40)
plt.plot(xx,yy,color='r', linewidth=1, alpha=0.6,marker='*')
plt.show()

# mmp 不想写了 弃坑